﻿<!DOCTYPE html>
<html>

<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>MPI实现矩阵乘法-Cannon算法</title>
  <link rel="stylesheet" href="https://stackedit.io/style.css" />
</head>

<body class="stackedit">
  <div class="stackedit__html"><h1 id="mpi实现矩阵乘法-cannon算法">MPI实现矩阵乘法-Cannon算法</h1>
<p><strong>计试61 张翀 2140506063</strong></p>
<h2 id="题目">题目</h2>
<p>使用MPI实现矩阵乘法。此处为了简单，只需使用MPI实现<code>n*n</code>方阵之间的乘法。</p>
<h2 id="思路">思路</h2>
<p>Cannon算法的思路：如果方阵的维度数是<code>a</code>的倍数，那么可以将方阵<code>a*a</code>分块，计算每一块的乘积只需要A的对应行和B的对应列。在这里，我们额外要求进程数为<code>a</code>，此时每个进程负责计算<code>a</code>个块，而且我们规定是每一行的<code>a</code>个块。<br>
应用这样分块的方法，可以减小进程中需要给临时乘数矩阵<code>partA</code>和<code>partB</code>分配的空间。比起正常的行列分发，消耗的内存减少为原来的<code>1/a</code>.</p>
<h2 id="代码">代码</h2>
<p>在这里，我们主要使用最基本的<code>Send</code>和<code>Recv</code>两条指令做数据的分发和接收。<br>
以下是<code>MPI_Send</code>的函数原型：</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token keyword">int</span> <span class="token function">MPI_Send</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>buf<span class="token punctuation">,</span> 
             <span class="token keyword">int</span> count<span class="token punctuation">,</span> 
             MPI_Datatype datatype<span class="token punctuation">,</span> 
             <span class="token keyword">int</span> goal<span class="token punctuation">,</span> 
             <span class="token keyword">int</span> tag<span class="token punctuation">,</span> 
             MPI_Comm comm
<span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre>
<p>对于需要分发的消息，需要指定源数据和数据类型；指定接收消息的进程之后，需要指定数据量和进程接收数据的位置指针。在MPI中，每一对<code>Send</code>和<code>Recv</code>是在系统中建立一个半双工信道，确认信息到达后关闭。为了管理这些通话，参数<code>tag</code>管理每个对话的ID.执行这条命令之后，按照进程号顺序，指定数据会分发给每一个进程。<br>
以下是<code>MPI_Gather</code>的函数原型：</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token keyword">int</span> <span class="token function">MPI_Recv</span><span class="token punctuation">(</span><span class="token keyword">void</span> <span class="token operator">*</span>buf<span class="token punctuation">,</span> 
             <span class="token keyword">int</span> count<span class="token punctuation">,</span> 
             MPI_Datatype datatype<span class="token punctuation">,</span> 
             <span class="token keyword">int</span> source<span class="token punctuation">,</span> 
             <span class="token keyword">int</span> tag<span class="token punctuation">,</span> 
             MPI_Comm comm，MPI_Status<span class="token operator">*</span>status
<span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre>
<p>参数基本相同，准备接收指定进程的数据，收到之后才能继续运行程序，否则一直阻塞。<br>
另外，主进程也要参与部分矩阵的计算，但是并不参与数据分发。数据是直接从A和B的对应位置拷贝到partA和partB的。</p>
<h2 id="程序代码">程序代码</h2>
<p>程序如下所示，在<code>a</code>次循环中，主进程把对应的行列发送给每个进程，每个进程依次计算自己对应行的矩阵块，计算完毕返回结果，主进程接收结果并重新赋值写入矩阵C.以下是程序中比较关键的几个设计点：<br>
1.主进程的部分矩阵直接通过赋值得到，而不通过通信，因为进程无法<code>Send</code>消息给自己；<br>
2.根据思路部分的分析，程序只允许完全平方数的进程数，如果输入的进程数不是完全平方数会报错；<br>
3.矩阵的维度数必须是<code>a</code>的倍数，用如下的程序确定矩阵的维度数：</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token keyword">if</span><span class="token punctuation">(</span>n <span class="token operator">%</span> comm_sz <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    n <span class="token operator">-</span><span class="token operator">=</span> n <span class="token operator">%</span> comm_sz<span class="token punctuation">;</span>
    n <span class="token operator">+</span><span class="token operator">=</span> comm_sz<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
<p>将扩大的矩阵部分全部填充为0，这样原来计算部分的计算结果不会出错。<br>
为了方便测试时间，设计函数<code>matGene</code>生成指定大小的矩阵，<code>vecGene</code>生成指定大小的向量，生成矩阵之后求乘积，再输出结果。<br>
完整的设计代码随附件提交。</p>

<div class="stackedit__html"></div>

<h2 id="实验结果">实验结果</h2>
<p>使用如下命令编译并执行：<code>mpicxx main.cpp &amp;&amp; mpiexec -n num_processes ./a.out mat_dim</code>，执行可执行文件时带的两个参数分别是矩阵维度和使用的进程数。<br>
在一台8核机器上进行测试，测试时间如下：</p>

<table>
<thead>
<tr>
<th align="center">进程数</th>
<th align="center">1</th>
<th align="center">4</th>
<th align="center">9</th>
</tr>
</thead>
<tbody>
<tr>
<td align="center">256 * 3</td>
<td align="center">1.8839</td>
<td align="center">0.368062</td>
<td align="center">0.285604</td>
</tr>
<tr>
<td align="center">512 * 3</td>
<td align="center">39.8575</td>
<td align="center">4.55514</td>
<td align="center">5.73879</td>
</tr>
</tbody>
</table><p>表格中最左侧一栏为测试时矩阵维度，表格中时间单位为秒。维度较小的数据测出的结果不具有说服力，维度较大的数据因硬件限制测出结果不能反映特性，此处挑了两组数据做解释。<br>
由数据可见两点：</p>
<ul>
<li>通过直线的大致斜率可见，矩阵乘法的算法是<span class="katex--inline"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>3</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^3)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 1.06em; vertical-align: -0.25em;"></span><span class="mord mathdefault" style="margin-right: 0.02em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.81em;"><span style="top: -3.06em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">3</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></span>的；</li>
<li>通过多进程并行执行程序，程序确实能获得对应的加速比。
<ul>
<li>4进程应该得到近似为4的加速比；</li>
<li>9进程中每个任务量为原任务的1/9，但多余的1个进程预期造成某个核执行2次子任务，所以总用时应该为2/9，即程序应该得到4.5的加速比。</li>
<li>在256 * 3维的测试中，基本上获得了我们的预期加速比，可能因为Cache耗尽，测得的1进程执行时间偏大；在512 * 3维的测试中，因为Cache耗尽，1进程和9进程的测试结果有较大偏差，但总体符合我们的加速比测算。</li>
</ul>
</li>
</ul>
</div>
</body>

</html>
